package pwd.allen;

/**
 * 快排
 * 原理：从数组中选择一个元素作为中轴，把小于中轴元素的元素放在其左边，大于或等于中轴元素的元素放在其右边，此时中轴元素所处的位置的是有序的。
 *  从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，
 *  让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。
 *
 * 时间复杂度：
 *  平均：O(nlog2n) 最坏：O(n^2) 最好：O(nlog2n)
 * 空间复杂度：O(nlog2n)
 * 稳定性：不稳定
 */
public class QuickSort {

    public void sortQuick(int[] array) {
        if (array.length > 1) {
            quick(array, 0, array.length - 1);
        }
    }

    private void quick(int[] array, int low, int high) {
        if (low < high) {
            int middle = getMiddle(array, low, high);
            quick(array, low, middle - 1);
            quick(array, middle + 1, high);
        }
    }

    /**
     * 以第一个元素作为中轴，小于中轴的放左边，大于中轴的放右边，然后返回此时中轴的索引位置
     * @param array
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] array, int low, int high) {
        //数组的第一个元素做为中轴
        int temp = array[low];
        while (low < high) {
            while (low < high && array[high] >= temp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= temp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = temp;
        return low;
    }

}